package fun.coding.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTreeLevelOrderTraversal {

    /**
     * @param args
     */
    public static void main(String[] args) {
    }
    
    /* See BinarySearchTreeImpl.java for details. 
     * 
        * 1) revised this by putting a '\n' in each level, whenever popping out '\n', a new '\n' would be inserted. 
        * 2) keep track of two queues, and keep switching them when one queue is empty and print out a space
        * 3) keep a current of current level and next level.
    */ 
    public List<List<Integer>> levelOrderTwoQueue(TreeNode root) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        
        if (root == null) return res;
        
        Queue<TreeNode> cur = new LinkedList<TreeNode>();
        Queue<TreeNode> next = new LinkedList<TreeNode>();
        
        cur.add(root);
        
        // There is difference between offer and add, in some implementations, they are the same.
        // In some queue size restriction, offer will return false while add will throws exception. 
        while (!cur.isEmpty()) {
        	// NOTE: stupid, don't need this 3rd queue :(
            Queue<TreeNode> temp = new LinkedList<TreeNode>();
            
            while (!cur.isEmpty()) {
                temp.add(cur.poll());
            }
            
            List<Integer> level = new LinkedList<Integer>();
            
            for (TreeNode n : temp) {
                level.add(n.val);
                
                if (n.left != null) {
                    next.add(n.left);
                }
                if (n.right != null) {
                    next.add(n.right);
                }    
            }
            
            res.add(level);
            
            cur = next;
            
        }
        
        return res;
        
    }
    // this uses only 1 queue
    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> res = new ArrayList<List<Integer>>();
    	if (root == null) return res;
    	
    	Queue<TreeNode> q = new LinkedList<TreeNode>();
    	q.add(root);
    	
    	while (!q.isEmpty()) {
    		int size = q.size();
    		List<Integer> temp = new ArrayList<Integer>();
    		
    		for (int i = 0; i < size; i++) {
    			TreeNode t = q.poll();
    			temp.add(t.val);
    			
    			if (t.left != null) q.add(t.left);
    			if (t.right != null) q.add(t.right);
    		}
    		res.add(temp);
    	}
    	
    	return res;
    }
    
}




